#pragma once

#include <cassert>
#include <algorithm>
#include <vector>

namespace solution_018
{

class Solution
{
public:
    std::vector< std::vector<int> > fourSum(std::vector<int>& nums, int target)
    {
        if ((int)nums.size() < m_size)
            return { };
        if ((int)nums.size() == m_size) {
            if (nums[0] + nums[1] + nums[2] + nums[3] == target)
                return { nums };
        }
        m_nums.swap(nums);
        std::sort(m_nums.begin(), m_nums.end());

        std::vector<int> quad;
        quad.reserve(m_size);
        nsum(quad, 0, target);
        return m_quad;
    }

private:
    void nsum(std::vector<int>& quad, int first, int target)
    {
        int rest = m_size - quad.size();
        if (rest == 2)
            return twosum(quad, first, m_nums.size() - 1, target);

        int tail_sum = 0;
        int head_sum = 0;
        for (int i = 1; i < rest; ++i) {
            head_sum += m_nums[i - 1];
            tail_sum += m_nums[m_nums.size() - i];
        }

        for (int i = first; i + rest - 1 < (int)m_nums.size(); ++i) {
            if (i > first && m_nums[i] == m_nums[i-1])
                continue;

            head_sum += m_nums[i + rest - 1];
            if (head_sum > target)
                break;
            head_sum -= m_nums[i];
            if (m_nums[i] + tail_sum < target)
                continue;

            quad.push_back(m_nums[i]);
            nsum(quad, i + 1, target - m_nums[i]);
            quad.pop_back();
        }
    }

    void twosum(std::vector<int>& quad, int first, int last, int target)
    {
        while (first < last) {
            int sum = m_nums[first] + m_nums[last];
            if (sum == target) {
                m_quad.push_back(quad);
                m_quad.back().push_back(m_nums[first]);
                m_quad.back().push_back(m_nums[last]);
                ++first;
                while (first < last && m_nums[first] == m_nums[first - 1])
                    ++first;
                --last;
                while (first < last && m_nums[last] == m_nums[last + 1])
                    --last;
            } else if (sum < target) {
                ++first;
                while (first < last && m_nums[first] == m_nums[first - 1])
                    ++first;
            } else {
                --last;
                while (first < last && m_nums[last] == m_nums[last + 1])
                    --last;
            }
        }
    }

    int m_size = 4;
    std::vector<int> m_nums;
    std::vector< std::vector<int> > m_quad;
};

}  /* namespace solution_018 */
